<html>
<head><meta charset="utf-8"><title>Floating-point operations are non-deterministic · t-compiler/wg-llvm · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/index.html">t-compiler/wg-llvm</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Floating-point.20operations.20are.20non-deterministic.html">Floating-point operations are non-deterministic</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="209759525"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Floating-point%20operations%20are%20non-deterministic/near/209759525" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> RalfJ <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Floating-point.20operations.20are.20non-deterministic.html#209759525">(Sep 11 2020 at 09:40)</a>:</h4>
<p><span class="user-mention" data-user-id="209168">@Thom Chiovoloni</span> just pointed me to <a href="https://webassembly.github.io/spec/core/exec/numerics.html">https://webassembly.github.io/spec/core/exec/numerics.html</a>, which has a lot of interesting things to say. I always love how precise wasm spcs are, I wish LLVM (or C or C++) would be even remotely as good.^^<br>
In particular, <a href="https://webassembly.github.io/spec/core/exec/numerics.html#nan-propagation">this</a> says that most of these operations (basically everything except for a fneg, fabs, or fcopysig) are non-deterministic. This means it would be incorrect for LLVM to change something like</p>
<div class="codehilite"><pre><span></span><code><span class="kd">let</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">f1</span><span class="w"> </span><span class="o">/</span><span class="w"> </span><span class="n">f2</span><span class="p">;</span><span class="w"></span>
<span class="n">function</span><span class="p">(</span><span class="n">f</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">);</span><span class="w"></span>
</code></pre></div>


<p>to</p>
<div class="codehilite"><pre><span></span><code><span class="n">function</span><span class="p">(</span><span class="n">f1</span><span class="w"> </span><span class="o">/</span><span class="w"> </span><span class="n">f2</span><span class="p">,</span><span class="w"> </span><span class="n">f1</span><span class="w"> </span><span class="o">/</span><span class="w"> </span><span class="n">f2</span><span class="p">);</span><span class="w"></span>
</code></pre></div>


<p>Basically, LLVM has to specify its own floating-point operations as non-deterministic as well, otherwise compilation to WASM is incorrect.</p>
<p>Does anyone know if there are circumstances under which LLVM might perform transformations like the above -- transformations that compute a value twice where in the source program it was computed only once?</p>



<a name="209818160"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Floating-point%20operations%20are%20non-deterministic/near/209818160" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Floating-point.20operations.20are.20non-deterministic.html#209818160">(Sep 11 2020 at 18:32)</a>:</h4>
<p>I'm curious how it would end up being "non-deterministic" rather than just "unspecified (but consistent for the same calculation)".</p>



<a name="209829547"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Floating-point%20operations%20are%20non-deterministic/near/209829547" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> RalfJ <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Floating-point.20operations.20are.20non-deterministic.html#209829547">(Sep 11 2020 at 20:13)</a>:</h4>
<p><span class="user-mention silent" data-user-id="239881">Josh Triplett</span> <a href="#narrow/stream/187780-t-compiler.2Fwg-llvm/topic/Floating-point.20operations.20are.20non-deterministic/near/209818160">said</a>:</p>
<blockquote>
<p>I'm curious how it would end up being "non-deterministic" rather than just "unspecified (but consistent for the same calculation)".</p>
</blockquote>
<p>me too -- but it's clearly what the spec says, so I suppose they have a good reason</p>



<a name="209829590"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Floating-point%20operations%20are%20non-deterministic/near/209829590" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> RalfJ <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Floating-point.20operations.20are.20non-deterministic.html#209829590">(Sep 11 2020 at 20:13)</a>:</h4>
<p>one possible way this might happen: some computations get folded at compile-time, and the compiler cannot predict the exact NaN bit pattern that will be used during real execution/interpretation</p>



<a name="209829651"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Floating-point%20operations%20are%20non-deterministic/near/209829651" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> RalfJ <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Floating-point.20operations.20are.20non-deterministic.html#209829651">(Sep 11 2020 at 20:14)</a>:</h4>
<p>or maybe JITed code and the slow-path interpreter could behave differently</p>



<a name="209830953"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Floating-point%20operations%20are%20non-deterministic/near/209830953" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jubilee <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Floating-point.20operations.20are.20non-deterministic.html#209830953">(Sep 11 2020 at 20:26)</a>:</h4>
<p>Yes, saying NaNs are non-deterministic is (probably) a practical concession to the fact that no one implements NaNs in a consistent fashion, thus telling programmers to assume NaN can become any other NaN makes it actually possible to program with floats without e.g. requiring a specific soft-float implementation to be correct.</p>



<a name="209832090"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Floating-point%20operations%20are%20non-deterministic/near/209832090" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Floating-point.20operations.20are.20non-deterministic.html#209832090">(Sep 11 2020 at 20:37)</a>:</h4>
<p><span class="user-mention silent" data-user-id="120791">RalfJ</span> <a href="#narrow/stream/187780-t-compiler.2Fwg-llvm/topic/Floating-point.20operations.20are.20non-deterministic/near/209829651">said</a>:</p>
<blockquote>
<p>or maybe JITed code and the slow-path interpreter could behave differently</p>
</blockquote>
<p>That's an excellent point.</p>



<a name="209832152"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Floating-point%20operations%20are%20non-deterministic/near/209832152" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Floating-point.20operations.20are.20non-deterministic.html#209832152">(Sep 11 2020 at 20:38)</a>:</h4>
<p>"We don't know how this'll get executed" is a pretty good reason.</p>



<a name="209832178"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Floating-point%20operations%20are%20non-deterministic/near/209832178" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Floating-point.20operations.20are.20non-deterministic.html#209832178">(Sep 11 2020 at 20:38)</a>:</h4>
<p>(And really, code should <em>not</em> care which NaN it gets.)</p>



<a name="209833823"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Floating-point%20operations%20are%20non-deterministic/near/209833823" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Floating-point.20operations.20are.20non-deterministic.html#209833823">(Sep 11 2020 at 20:52)</a>:</h4>
<p>It's not clear to me why this would force LLVM to preserve those non-deterministic results though.</p>



<a name="209834253"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Floating-point%20operations%20are%20non-deterministic/near/209834253" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Floating-point.20operations.20are.20non-deterministic.html#209834253">(Sep 11 2020 at 20:56)</a>:</h4>
<p>Oh, wait, I read <span class="user-mention" data-user-id="120791">@RalfJ</span>'s example backward, as if LLVM were collapsing repeated divisions into one.</p>



<a name="209834348"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Floating-point%20operations%20are%20non-deterministic/near/209834348" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Floating-point.20operations.20are.20non-deterministic.html#209834348">(Sep 11 2020 at 20:57)</a>:</h4>
<p>But if LLVM introduces that repetition, non-determinism makes that incorrect.</p>



<a name="209852327"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Floating-point%20operations%20are%20non-deterministic/near/209852327" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Floating-point.20operations.20are.20non-deterministic.html#209852327">(Sep 12 2020 at 01:19)</a>:</h4>
<p>Non-determinism still allows the CSE, right?  Just not the opposite?</p>



<a name="209852518"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Floating-point%20operations%20are%20non-deterministic/near/209852518" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Floating-point.20operations.20are.20non-deterministic.html#209852518">(Sep 12 2020 at 01:24)</a>:</h4>
<p>I think CSE is fine, but that's what I was confused about</p>



<a name="209870659"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Floating-point%20operations%20are%20non-deterministic/near/209870659" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> RalfJ <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Floating-point.20operations.20are.20non-deterministic.html#209870659">(Sep 12 2020 at 08:15)</a>:</h4>
<p>yes, you can merge two computations that <em>could</em> produce the same result. that's reducing non-determinism which is okay.</p>



<a name="209870667"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Floating-point%20operations%20are%20non-deterministic/near/209870667" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> RalfJ <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Floating-point.20operations.20are.20non-deterministic.html#209870667">(Sep 12 2020 at 08:15)</a>:</h4>
<p>but you cannot repeat a computation as that increases non-determinism and thus introduces new program behavior, which is the one thing a compiler is not allowed to do</p>



<a name="209870669"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Floating-point%20operations%20are%20non-deterministic/near/209870669" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> RalfJ <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Floating-point.20operations.20are.20non-deterministic.html#209870669">(Sep 12 2020 at 08:15)</a>:</h4>
<p>so is LLVM aware of this limitation?</p>



<a name="209870712"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Floating-point%20operations%20are%20non-deterministic/near/209870712" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> RalfJ <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Floating-point.20operations.20are.20non-deterministic.html#209870712">(Sep 12 2020 at 08:16)</a>:</h4>
<p>(all this assumes that LLVM's FP operations are directly lowered to wasm's, which I assume to be true but wouldn't exactly know how to check)</p>



<a name="212675532"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Floating-point%20operations%20are%20non-deterministic/near/212675532" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Thom Chiovoloni <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Floating-point.20operations.20are.20non-deterministic.html#212675532">(Oct 08 2020 at 11:28)</a>:</h4>
<p>I came across <a href="https://github.com/WebAssembly/design/blob/master/Rationale.md#nan-bit-pattern-nondeterminism">https://github.com/WebAssembly/design/blob/master/Rationale.md#nan-bit-pattern-nondeterminism</a> (and Also see <a href="https://github.com/WebAssembly/design/blob/master/Nondeterminism.md">https://github.com/WebAssembly/design/blob/master/Nondeterminism.md</a>) which is interesting.</p>
<blockquote>
<p>IEEE 754-2008 6.2 says that instructions returning a NaN should return one of their input NaNs. In WebAssembly, implementations may do this, however they are not required to. Since IEEE 754-2008 states this as a "should" (as opposed to a "shall"), it isn't a requirement for IEEE 754-2008 conformance.</p>
</blockquote>
<p>This answers a lot of questions for <a href="https://github.com/rust-lang/rust/issues/73328">https://github.com/rust-lang/rust/issues/73328</a></p>
<p>Specifcally the way it wors is: Certain instructions are not guaranteed to preserve the payload bitpattern (in practice you can't rely on this portably so it seems fine that not to guarantee anything). Specifically:</p>
<ul>
<li>
<p>the instructions fsqrt, fceil, ffloor, ftrunc, fnearest, fadd, fsub, fmul, fdiv, fmin, fmax, promote (<code>f32 as f64</code>) and demote (<code>f64 as f32</code>): : do not preserve the payload or sign bits for non-canonical nans, and do not preserve the sign bit for canonical nans (where "do not preserve means "set to a nondeterministic value").</p>
</li>
<li>
<p>the instructions fneg, fabs, and fcopysign (e.g. "sign bit operations" according to ieee754) fully preserve nan payload, and only modify the sign bit if expected for the operation, and introduce no nondeterminsim. (this is actually a hard requirement of IEEE754 so it's not surprising if they're going with the "technically compliant" argument lol)</p>
</li>
</ul>
<p>All other operations, such as copying values around, loading/storing them to memory, roundtripping arbitrary bitpatterns (including the patterns of noncanonical nans) through float values, using them as args, returning them from functions... these should all preserve sign and payload of nans.</p>
<p>As I mentioned before you can't portably rely on what happens to these NaN payloads if you do math on them, so I don't think what's there is a big deal if this is followed. My big concern was mostly that that last set of things wouldn't work.</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>